package alg.list;

import java.util.ArrayList;
import java.util.List;

/**
 * @author:yuziji
 * @create: 2023-04-26 10:54
 * 判断一个链表是否是回文链表
 * 回文：从前往后看和从后往前看结果相同
 */
public class HuiWenNode {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(2);
        head.next.next.next = new Node(1);
        boolean is = isHuiWenToList(head);
        System.out.println(is);
    }


    /**
     * 先将链表转成list
     * 用两个指针i,j，一个从list的头开始，一个从list的尾开始遍历list
     * 如果list.get(i)!=list.get(j)说明不是回文链表
     * 循环结束条件：i<=j;
     * @param head
     * @return
     */
    private static boolean isHuiWenToList(Node head){
        List<Integer> list = new ArrayList<>();
        boolean isHuiWen = true;
        while(head!=null){
            list.add(head.value);
            head = head.next;
        }
        for (int i = 0, j = list.size()-i-1; i <= j ; i++,j--) {
            if (list.get(i)!=list.get(j)){
                isHuiWen = false;
                break;
            }
        }
        return isHuiWen;
    }

}
